package interview;

import java.util.*;

public class lc239_滑动窗口最大值 {
    public static void main(String[] args) {
        int[] ans = maxSlidingWindow1(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        //优先队列解法,排序入队
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            return  b[0] - a[0];
        });
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int t = 0;
        for (int i = 0; i < n; ++i) {
            queue.offer(new int[]{nums[i], i});
            //移除堆顶超过窗口左边的元素
            while (!queue.isEmpty() && queue.peek()[1] <= i - k) {
                queue.poll();
            }
            if(i >= k - 1)
                ans[t++] = queue.peek()[0];
        }
        return ans;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        //单调队列，队列里面存放下标，维护一个单调递减的队列，队首就是当前窗口的最大值
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] ans = new int[n - k + 1];
        int t = 0;
        for (int i = 0; i < n; i++) {
            //维持队列的单调性，队首最大
            while(!deque.isEmpty() && nums[deque.getLast()] <= nums[i])
                deque.removeLast();
            deque.addLast(i);
            //移除超出左边界的数据
            while(!deque.isEmpty() && deque.getFirst() <= i - k){
                deque.removeFirst();
            }
            if(i >= k - 1)
                ans[t++] = nums[deque.getFirst()];
        }
        return ans;
    }
}
